/*
 * @Author: liusheng
 * @Date: 2022-04-29 20:23:32
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-19 23:11:52
 * @Description: 剑指 Offer II 050. 向下的路径节点之和
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 050. 向下的路径节点之和
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

 

示例 1：



输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
 

提示:

二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109 
-1000 <= targetSum <= 1000 
 

注意：本题与主站 437 题相同：https://leetcode-cn.com/problems/path-sum-iii/

通过次数11,219 提交次数18,622
 */

#include "header.h"
// Definition for a binary tree node.
struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/*
Time:O(N^2)
Space:O(N) ---stack overhead
*/
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if (!root)
        {
            return 0;
        }
        
        //preorder traverse,every traverse invoke rootSum
        //to caculate result from that node
        int resFromRoot = rootSum(root,targetSum);
        resFromRoot += pathSum(root->left,targetSum);
        resFromRoot += pathSum(root->right,targetSum);
        
        return resFromRoot;
    }
private:
    //start from root(included),caculate the sum satisfied the 
    //targetSum
    int rootSum(TreeNode* root, long targetSum)
    {
        if (!root)
        {
            return 0;
        }
        
        int num = 0;
        if (root->val == targetSum)
        {
            num = 1;
        }
        
        long remainSum = targetSum - root->val;
        return num + rootSum(root->left,remainSum) + rootSum(root->right,remainSum);
    }
};

/*
Prefix Sum solution
*/
class Solution2 {
public:
    int pathSum(TreeNode* root, int targetSum) {
        sumPrefix[0] = 1;
        return dfsSumCount(root,0,targetSum);
    }
private:
    int dfsSumCount(TreeNode * root,long preSum,int targetSum)
    {
        if (!root)
        {
            return 0;
        }

        long currentSum = preSum + root->val;
        int cnt = 0;
        //if prefixSum has value equal to currentSum - targetSum
        if (sumPrefix.count(currentSum - targetSum))
        {
            cnt = sumPrefix[currentSum - targetSum];
        }

        //add this sum to sumPrefix
        ++sumPrefix[currentSum];
        cnt += dfsSumCount(root->left,currentSum,targetSum);
        cnt += dfsSumCount(root->right,currentSum,targetSum);

        //after traverse this node,sumPrefix[preSum]--
        --sumPrefix[currentSum];

        return cnt;
    }
private:
   unordered_map<long,int> sumPrefix;
};